package leetcode_800;

import java.util.Arrays;
import java.util.Comparator;

/**
 *@author 周杨
 *SetIntersectionSizeAtLeastTwo_757 给定N个区间 最终要求出一个区间的最小长度 但是这个区间使得每个区间都有至少两个元素在里面
 *describe:先排序 后用贪心算法解 AC 45%
 *2018年10月18日 上午10:48:13
 */
public class SetIntersectionSizeAtLeastTwo_757_ {
	
	public static void main(String[] args) {
		SetIntersectionSizeAtLeastTwo_757_ test=new SetIntersectionSizeAtLeastTwo_757_();
		test.intersectionSizeTwo(new int[][] {{5,6},{1,3},{2,4},{1,4}});
	}
	
	public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] != b[1] ? a[1]-b[1] : b[0]-a[0]); // java8 functional way of sort
        int sndMax = -2, max = -1, cnt = 0; // pay attention to intial values of sndMax and max
        for (int[] interval: intervals) {
            int start = interval[0], end = interval[1]; // check the validity before processing
            if (start <= sndMax ) { // two point overlapped
                continue;
            } else if (start <= max) { // one point overlapped
                cnt += 1;
                sndMax = max;
                max = end; 
            } else { // no point overlapped
                cnt += 2;
                sndMax = end - 1;
                max = end;
            }
        }
        return cnt;
    }
	
	/**
	 * describe:不知道哪里错了 最后一个用例没有过
	 * 2018年10月18日 上午10:39:05
	 */
	public int intersectionSizeTwo1(int[][] intervals) {
        Arrays.sort(intervals,new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1]-o2[1]>0)return 1;
				else if(o1[1]-o2[1]<0) return -1;
				else {
					return o1[0]-o2[0];

				}
			}
		});
        int left=-1,right=-1,res=0;//这个left right 并不是最终区间
        for(int[] interval:intervals) {
        	if(interval[0]<=left) continue;//大区间包含小区间
        	if(interval[0]>right) {//完全不包含
        		res+=2;
        		right=interval[1];
        		left=right-1;
        	}
        	else {//包含一个
        		++res;
        		left=right;
        		right=interval[1];
        	}
        }
        return res;
        
    }
}
